Many companies use formal design techniques in system development processes, including techniques for formally specifying system behavior using state machines. In the past, state machines were typically represented using state machine tables and manually drawn state machines. Although such tables are easily stored and processed by computers, and many details may be specified within such tables in a readable format, large tables are not easily understood by design engineers. In an effort to simplify system design processes for design engineers, graph layout and graphical display generation algorithms have been developed which translate a tabular representation of a state machine into a graphical representation of the state machine. There are currently three primary categories of graph layout algorithms: hierarchical layout algorithms, radial layout algorithms, and physical model algorithms.
The hierarchical layout algorithms assign nodes of a graph to discrete levels, and order the nodes of each level to avoid edge-crossing. The radial layout algorithms place a node specified as the center of the layout, and place the remaining nodes on a series of concentric circles around the center node. Disadvantageously, hierarchical and radial layout algorithms only achieve good results if the graph for which the layout is determined has specific properties, such as being acyclic or directed, which cannot be guaranteed for all graphs, and especially for finite state machines. Furthermore, hierarchical and radial layout algorithms cannot pin nodes to specific positions, thereby preventing dynamic updates between tabular and graphical representations of the graph without disturbing portions of the graph which may have been set manually.
The physical model algorithms treat nodes as physical objects influenced by force, and the layout is derived by finding the positions of the nodes. The most common physical model algorithms include the Kamada-Kawai and Frutchermann-Reingold algorithms. Disadvantageously, existing physical model algorithms model nodes as ideal points; however, since nodes typically include information (e.g., respective labels of the nodes) which must be visible in the graphical representation of the layout of the graph, modeling of the nodes as ideal points often results in significant overlaps which render such information unreadable. Although overlaps can be corrected, such corrections require additional processing on the layout of the graph, thereby increasing time and cost associated with generating and displaying the layout of the graph.